package com.practice.string;

import java.util.Arrays;

/**
 * Given a string of lowercase characters, reorder them such that the same 
 * characters are at least distance d from each other.
 * 
 * Input: { a, b, b }, distance = 2
 * Output: { b, a, b } 
 *
 */
public class ShuffleWordByDistance {
	public String shuffle(String a, int distance) {
		int N = a.length();
		Char[] set = new Char[256];
		for (char i=0; i<256; i++) {
			set[i] = new Char();
			set[i].value = i;
		}
		
		char[] cs = a.toCharArray();
		for (char c : cs) {
			set[c].count++;
		}
		
		char[] s = new char[N];
		for (int i=0; i<N; i++) {
			Arrays.sort(set);
			int j = 0;
			while (set[j].last + distance > i) j++;
			if (set[j].count == 0) return null;
			
			s[i] = set[j].value;
			set[j].count--;
			set[j].last = i;
		}
		
		return new String(s);
	}
	
	private class Char implements Comparable {
		char 	value;
		int		count;
		int		last = Integer.MIN_VALUE;
		@Override
		public int compareTo(Object c) {
			return ((Char)c).count - this.count;
		}
	}
}
